package main.java.LeetCode.SolutionVersionTwo;



import main.java.LeetCode.CommonSolution.ListNode;
import main.java.LeetCode.CommonSolution.TreeNode;

import javax.print.DocFlavor;
import java.util.*;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.Collectors;
import java.util.stream.Stream;

@SuppressWarnings("ALL")
public class Solution {
    private Map<Integer, Integer> indexMap;
    int TreeNodeSum = 0;
    public Map<TreeNode,Integer> NotGetMap;
    public Map<TreeNode,Integer> GetMap;

    HashMap<String, Set<String>> map = new HashMap<>();
    HashMap<String, Boolean> isRouter = new HashMap<>();
    HashMap<String, Double> valMap = new HashMap<>();
    HashSet<String> ISexist = new HashSet<String>();

    HashMap<TreeNode,Integer> treeMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return TreeBuilder(preorder, 0, n - 1, 0, n - 1);

    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        int preorder_root = preorder_left;
        int inorder_root = indexMap.get(preorder[preorder_root]);
        TreeNode root = new TreeNode(preorder[preorder_root]);
        int size_left_subtree = inorder_root - inorder_left;
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    private TreeNode TreeBuilder(int[] pre, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight)
            return null;
        int inRootVal = pre[preLeft];
        TreeNode root = new TreeNode(inRootVal);
        int inRootIndex = indexMap.get(inRootVal);
        int LeftSubTreeLength = inRootIndex - inLeft;
        int RightSubTreeLength = inRight - inRootIndex;
        root.left = TreeBuilder(pre, preLeft + 1, preLeft + LeftSubTreeLength, inRootIndex - LeftSubTreeLength, inRootIndex - 1);
        root.right = TreeBuilder(pre, preLeft + LeftSubTreeLength + 1, preLeft + LeftSubTreeLength + RightSubTreeLength, inRootIndex + 1, inRootIndex + RightSubTreeLength);
        return root;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        return null;
    }

    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int index = -1;
        int maxNums = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int num = map.getOrDefault(nums[i], 0) + 1;
            if (num == nums.length / 2 + 1)
                return nums[i];
            map.put(nums[i], num);
            if (num >= maxNums) {
                maxNums = num;
                index = nums[i];
            }
        }
        return index;
    }

    public ListNode sortList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if (head.next == null)
            return head;
        while (fast.next != null) {
            if (fast.next.next == null) {
                fast = fast.next;
                break;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode headR = sortList(slow.next);
        slow.next = null;
        ListNode headL = sortList(head);
        ListNode node = mergeTwoLists(headL, headR);

        return node;
    }


    public int[] mergeSort(int[] nums, int l, int h) {
        if (l == h)
            return new int[]{nums[l]};

        int mid = l + (h - l) / 2;
        int[] leftArr = mergeSort(nums, l, mid);
        int[] rightArr = mergeSort(nums, mid + 1, h);
        int[] newNum = new int[leftArr.length + rightArr.length];

        int m = 0, i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length)
            newNum[m++] = leftArr[i++];
        while (j < rightArr.length)
            newNum[m++] = rightArr[j++];
        return newNum;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode tempHead = head;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tempHead.next = list1;
                list1 = list1.next;
            } else {
                tempHead.next = list2;
                list2 = list2.next;
            }
            tempHead = tempHead.next;

        }

        ListNode node = list1 == null ? list2 : list1;
        tempHead.next = node;

        return head.next;
    }

    public int numIslands(char[][] grid) {
        int numsOfLand = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    numsOfLand++;
                    killLand(grid, i, j);
                }

            }
        }
        return numsOfLand;
    }
    private void killLand(char[][] grid, int i, int j) {
        if (grid[i][j] == '1') {
            grid[i][j] = '0';
            if (i - 1 >= 0)
                killLand(grid, i - 1, j);
            if (i + 1 < grid.length)
                killLand(grid, i + 1, j);
            if (j - 1 >= 0)
                killLand(grid, i, j - 1);
            if (j + 1 < grid[0].length)
                killLand(grid, i, j + 1);
        } else
            return;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        boolean[][] route = new boolean[numCourses][numCourses];
        int[][] courses = new int[numCourses][numCourses];
        boolean[] isLearn = new boolean[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            courses[prerequisites[i][0]][prerequisites[i][1]] = 1;
        }
        for (int i = 0; i < numCourses; i++) {
            if (!isLearn[i]) {
                for (int j = 0; j < numCourses; j++) {
                    if (courses[i][j] == 1 && !isLearn[j]) {
                        route[i][j] = true;
                        if (!findCourseIsOK(courses, route, j, isLearn)) {
                            return false;
                        } else
                            route[i][j] = false;

                    }
                }
                isLearn[i] = true;
            } else
                continue;

        }

        return true;
    }

    private boolean findCourseIsOK(int[][] courses, boolean[][] router, int indexR, boolean[] isLearn) {
        if (isLearn[indexR])
            return true;
        for (int i = 0; i < courses.length; i++) {
            if (courses[indexR][i] == 1 && router[indexR][i])
                return false;
            if (courses[indexR][i] == 1 && !isLearn[i]) {
                router[indexR][i] = true;
                if (!findCourseIsOK(courses, router, i, isLearn))
                    return false;
                else
                    router[indexR][i] = false;
            }
        }
        isLearn[indexR] = true;
        return true;
    }

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i : nums) {
            if (queue.size() < k) {
                queue.add(i);
                continue;
            }
            if (queue.size() == k && queue.peek() < i) {
                queue.poll();
                queue.add(i);
            }
        }
        return queue.peek();
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;
        TreeNode rightRoot = invertTree(root.right);
        TreeNode leftRoot = invertTree(root.left);
        if (rightRoot == null && leftRoot == null)
            return root;
        root.right = leftRoot;
        root.left = rightRoot;
        return root;
    }

    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        boolean isOdd = true;
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (fast.next != null) {
            arrayList.add(slow.val);
            if (fast.next.next == null) {
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        System.out.println(arrayList);
        ListNode backHead = slow.next;
        for (int i = arrayList.size() - 1; i >= 0; i--) {
            if (arrayList.get(i) != backHead.val)
                return false;
            backHead = backHead.next;
        }
        return true;

    }

    public void moveZeroes(int[] nums) {
        int a = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0 && a == -1) {
                a = i;
                continue;
            }

            if (nums[i] != 0 && a != -1) {
                nums[a] = nums[i];
                nums[i] = 0;
                a++;
            }
        }


        for (int i : nums) {
            System.out.print(i + " ");
        }
    }

    public int[] countBits(int n) {
        int[] ints = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = 0;
            int temp = i;
            while (temp != 0) {
                if ((temp & 1) == 1) {
                    count++;
                }
                temp = temp >> 1;
            }
            ints[i] = count;
        }
        return ints;
    }

    public List<Integer> findDisappearedNumbers(int[] nums) {
//        boolean[] isExist = new boolean[nums.length + 1];
        ArrayList<Integer> list = new ArrayList<>();
//        for (int i = 0; i < nums.length; i++) {
//            int index = nums[i];
//            isExist[index] = true;
//        }
//        for (int i = 1; i < isExist.length; i++) {
//            if (!isExist[i])
//                list.add(i);
//        }
        for(int i = 0;i<nums.length;i++){
            int index = Math.abs(nums[i])-1;
            if(nums[index]>0)
                nums[index] = -nums[index];
        }
        for(int i = 0;i<nums.length;i++){
            if(nums[i]>0)
                list.add(i+1);
        }
        return list;

    }

    public int hammingDistance(int x,int y){
        int res = x^y;
        int count = 0;
        while (res!=0){
            if((res&1)==1)
                count++;
            res = res>>1;
        }
        return count;
    }

    public int diameterOfBinaryTree(TreeNode root){
        HashMap<Integer, Integer> map = new HashMap<>();
        TreeSet<Integer> set = new TreeSet<>();
        int max = findMaxDistantceInTree(root,set);
        System.out.println(max);
        System.out.println(set);
        return set.last();
    }
    private int findMaxDistantceInTree(TreeNode root,Set<Integer> set){
        if(root==null)
            return -1;
        int right = findMaxDistantceInTree(root.right,set)+1;
        int left = findMaxDistantceInTree(root.left,set)+1;
        System.out.println(root.val+": left: "+left+" right: "+right);
        set.add(right+left);
        return right>left?right:left;
    }

    public TreeNode mergeTrees(TreeNode root1,TreeNode root2){
        if(root2==null||root1==null)
            return root1==null?root2:root1;
        return merge(root1,root2);
    }
    private TreeNode merge(TreeNode root1,TreeNode root2){
        if(root2==null||root1==null)
            return null;
        root2.val = root2.val+root1.val;
        if(merge(root1.left,root2.left)==null){
            if(root2.left==null)
                root2.left = root1.left;
        }
        if(merge(root1.right,root2.right)==null){
            if(root2.right==null)
                root2.right = root1.right;
        }
        return root2;
    }

    public int subarraySum(int[] nums,int k){
        int count = 0;
        int sum = 0;
        for(int i = 0;i<nums.length;i++)
        {
            for(int j = i;j<nums.length;j++)
            {
                sum = sum+nums[j];
                if(sum == k)
                {
                    count++;
                }
            }
            sum = 0;
        }
        return count;
    }
    public int subarraySumBetter(int[] nums,int k){
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        HashMap<TreeNode, TreeNode> map = new HashMap<>();
        map.put(root,null);
        findTreeNode(root,map);
        TreeNode tempNode  = p;
        HashSet<TreeNode> set = new HashSet<>();
        while (true)
        {
            set.add(tempNode);
            tempNode = map.get(tempNode);
            if(tempNode==null)
                break;
        }
        tempNode = q;
        while (true)
        {
            if(set.contains(tempNode))
                return tempNode;
            tempNode = map.get(tempNode);
            if (tempNode == null)
                break;
        }
        return null;
    }
    private void findTreeNode(TreeNode root,HashMap<TreeNode,TreeNode> map){

        if(root.left!=null){
            map.put(root.left,root);
            findTreeNode(root.left,map);
        }
        if(root.right!=null){
            map.put(root.right,root);
            findTreeNode(root.right,map);
        }

    }

    public int[] productExceptSelf(int[] nums){
        int[] ans = new int[nums.length];
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        left[0] =1;
        right[nums.length-1] = 1;
        int rightPoint = nums.length-2;
        for(int i = 1;i<nums.length;i++)
        {
            left[i] = nums[i-1]*left[i-1];
            right[rightPoint] = nums[rightPoint+1]*right[rightPoint+1];
            rightPoint--;
        }
        for(int i = 0;i<nums.length;i++){
//            System.out.println("left: "+left[i]+" right: "+right[i]);
            ans[i] = left[i]*right[i];
        }
        return ans;
    }

    public int rob(TreeNode root){
        NotGetMap = new HashMap<>();
        GetMap = new HashMap<>();

        int sum1 = robMax(root.left,true)+robMax(root.right,true)+root.val;
        int sum2 = robMax(root.left,false)+robMax(root.right,false);
        return sum1>sum2?sum1:sum2;
//        while (true)
//        {
//            if(listR.isEmpty()&&!listL.isEmpty())
//            {
//                while (!listL.isEmpty())
//                {
//                    TreeNode e = listL.poll();
//                    if(e.right!=null)
//                        listR.offer(e.right);
//                    if(e.left!=null)
//                        listR.offer(e.left);
//                }
//            }
//            else if (!listR.isEmpty() && listL.isEmpty())
//            {
//                while (!listR.isEmpty())
//                {
//                    TreeNode e = listR.poll();
//                    if(flag)
//                        sumLeft = sumLeft+e.val;
//                    else
//                        sumRight =sumRight+e.val;
//                    listL.offer(e);
//                }
//                if(flag)
//                {
//                    arrayList.add(sumLeft);
//                    sumLeft = 0;
//                }else {
//                    arrayList.add(sumRight);
//                    sumRight = 0;
//                }
//
//                flag = flag?false:true;
//
//            }
//            else
//            {
//                return Math.max(robMax(arrayList,arrayList.get(0),true,1),robMax(arrayList,0,false,1));
//            }
//        }re
    }
    private int robMax(TreeNode root ,boolean isGet){
        if(root==null)
            return 0;
        if(isGet)
        {
            if(NotGetMap.get(root)==null)
            {
                int sum1 = robMax(root.left,false)+robMax(root.right,false);
                NotGetMap.put(root,sum1);
                return sum1;
            }
            else
                return NotGetMap.get(root);
//            return robMax(root.left,false)+robMax(root.right,false);
        }
        else {
            if(GetMap.get(root)==null)
            {
                int sum1 = robMax(root.left,true)+robMax(root.right,true)+root.val;
                GetMap.put(root,sum1);
            }
            if(NotGetMap.get(root)==null)
            {
                int sum2 = robMax(root.left,false)+robMax(root.right,false);
                NotGetMap.put(root,sum2);
            }
//            int sum1 = robMax(root.left,true)+robMax(root.right,true)+root.val;
//            int sum2 = robMax(root.left,false)+robMax(root.right,false);
            return GetMap.get(root)>NotGetMap.get(root)?GetMap.get(root):NotGetMap.get(root);
        }


    }

    public int findTargetSumWays(int[] nums,int target){
        int[] counter = new int[1];
        counteSumWays(nums,target,0,counter,0);
        return counter[0];
    }
    private void counteSumWays(int[] nums,int target,int sum,int[] counter,int i){
//        if(sum>target)
//            return;
        if(i==nums.length)
        {
            if(sum==target)
            {
                counter[0]++;
                return;
            }
            else
                return;
        }
        counteSumWays(nums,target,sum-nums[i],counter,i+1);
        counteSumWays(nums,target,sum+nums[i],counter,i+1);
    }

    public TreeNode converBST(TreeNode root){
        SumTree(root);
        return root;
    }
    private void SumTree(TreeNode root){
        if(root==null)
            return;
        SumTree(root.right);
        root.val = root.val+TreeNodeSum;
        TreeNodeSum = root.val;
        SumTree(root.left);
    }

    public int[] dailyTemperatures(int[] temperatures) {
        LinkedList<Integer> list = new LinkedList<>();
        list.push(0);
        int[] ans = new int[temperatures.length];

        for (int i = 1; i < temperatures.length; i++) {
            if (temperatures[i] > temperatures[list.peek()]) {
                while (!list.isEmpty() && temperatures[i] > temperatures[list.peek()]) {
                    ans[list.peek()] = i - list.peek();
                    list.pop();
                }
            }
            list.push(i);
        }
        return ans;
    }

    public List<Integer> findAnagrams(String s,String p){
        int charSum = 0;
        int subStrSum = 0;
        ArrayList<Integer> list = new ArrayList<>();
        if(p.length()>s.length())
            return list;

        char[] charP = p.toCharArray();
        Arrays.sort(charP);
        p = new String(charP);

        for(int i = 0;i<s.length();i++)
        {
            if(i<p.length())
            {
                subStrSum = subStrSum+(int)s.charAt(i);
                charSum = charSum+(int)p.charAt(i);
                if(i == p.length()-1&&subStrSum==charSum){
                    char[] charS = s.substring(0,i+1).toCharArray();
                    Arrays.sort(charS);
                    String subString = new String(charS);
                    if(subString.equals(p))
                        list.add(0);
                }
                continue;
            }
            subStrSum = subStrSum+(int)s.charAt(i) - (int)s.charAt(i-p.length());
            if(subStrSum==charSum)
            {
                char[] charS = s.substring(i-p.length()+1,i+1).toCharArray();
                Arrays.sort(charS);
                String subString = new String(charS);
                if(subString.equals(p))
                    list.add(i-p.length()+1);
            }
        }
        return list;
    }

    public void sortColors(int[] nums){
        quickSort(nums,0,nums.length-1);
    }
    private void quickSort(int[] nums,int left,int right){
        if(left>right)
            return;

        int baseNum = nums[left];
        int head =left;
        int tail = right;

        while(left<right) {
            while (baseNum<=nums[right]&&left<right)
                right--;
            while (baseNum>=nums[left]&&left<right)
                left++;
            if(left<right)
                swap(nums,left,right);
        }
        nums[head] = nums[left];
        nums[left] = baseNum;
        quickSort(nums,head,right-1);
        quickSort(nums,right+1,tail);

    }
    private void swap(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public void rotate(int[][] matrix){

    }

    /**桶思想**/
    public int leastInterval(char[] tasks,int n){
        int[] temp = new int[26];
        int countMaxTask = 0;
        int maxTask=0;
        for(char c:tasks){
            temp[c-'A']++;
            maxTask = Math.max(temp[c-'A'],maxTask);
        }
        for(int i=0;i<26;i++){
            if(temp[i]==maxTask){
                countMaxTask++;
            }
        }
        return Math.max(tasks.length,(maxTask-1)*(n+1)+countMaxTask);
    }

    public int[][] reconstructQueue(int[][] people){
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0])
                    return o1[1]-o2[1];
                else
                    return o2[0] - o1[0];
            }
        });
        LinkedList<int[]> tempStack = new LinkedList<>();
        LinkedList<int[]> Stack = new LinkedList<>();
        int ArraySize = people.length-1;
        int[][] resPeople = new int[ArraySize+1][2];
        System.out.println(Stack.size());
        for(int[] a:people){
            System.out.println(a[0]+" "+a[1]);
        }
        System.out.println("------------------");

        for(int[] a:people) {

            if(a[1]<Stack.size())
            {
                while (Stack.size()>a[1])
                {
                    int[] tempP = Stack.pop();
                    tempStack.push(tempP);
                }
            }
            if(a[1]>Stack.size())
            {
                while (Stack.size()<a[1])
                {
                    int[] tempP = tempStack.pop();
                    Stack.push(tempP);
                }
            }
            Stack.push(a);
        }
        if(!tempStack.isEmpty()||!Stack.isEmpty())
        {
            while (!tempStack.isEmpty())
            {
                int[] tempP = tempStack.pollLast();
                System.out.println(tempP[0]+" "+tempP[1]);
                resPeople[ArraySize][0] = tempP[0];
                resPeople[ArraySize][1] = tempP[1];
                ArraySize--;
            }
            while (!Stack.isEmpty())
            {
                int[] tempP = Stack.pop();
                System.out.println(tempP[0]+" "+tempP[1]);
                resPeople[ArraySize][0] = tempP[0];
                resPeople[ArraySize][1] = tempP[1];
                ArraySize--;
            }
        }


        return resPeople;
    }

    public int[] topKFrequent(int[] nums,int k){
        int[] res = new int[k];
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i:nums){
            map.put(i,map.getOrDefault(i,0)+1);
        }
        if(k>map.size())
            return res;
        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        Stream<Map.Entry<Integer, Integer>> entryStream = set.stream().sorted(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });
        List<Map.Entry<Integer, Integer>> list = entryStream.collect(Collectors.toList());
        for(Map.Entry<Integer,Integer> entry: list) {
            if(k == 0)/**/
                break;
            res[k-1] = entry.getKey();
            k--;
        }

        System.out.println(list);
        return res;
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries){

        double[] resArrays = new double[queries.size()];
        int flag = 0;

        for(List<String>list:equations)
        {
            String key = list.get(0);
            String value = list.get(1);
            System.out.println(key+" "+value);

            Set<String> set = map.getOrDefault(key,new HashSet<String>());
            set.add(value);
            map.put(key,set);
            valMap.put(key+"@"+value,values[flag]);

            set = map.getOrDefault(value,new HashSet<String>());
            set.add(key);
            map.put(value,set);
            valMap.put(value+"@"+key,1/values[flag]);

            isRouter.put(list.get(1),isRouter.getOrDefault(list.get(1),false));
            isRouter.put(list.get(0),isRouter.getOrDefault(list.get(0),false));

            ISexist.add(list.get(0));
            ISexist.add(list.get(1));
            flag++;
        }
        System.out.println(map);
        System.out.println(valMap);
        System.out.println(ISexist);
        flag = 0;

        for(List<String> list:queries){
            String key = list.get(0);
            String val = list.get(1);
            if(!ISexist.contains(key)||!ISexist.contains(val))
            {
                resArrays[flag] = -1;
                flag++;
                continue;
            }
            if(key.equals(val))
            {
                resArrays[flag] = 1;
                flag++;
                continue;
            }
            if(map.containsKey(key))
            {
                isRouter.replace(key,true);
                double res = findValue(key,val,1.0);
                isRouter.replace(key,false);
                resArrays[flag] = res;

                if(res!=-1){
                    map.get(key).add(val);
                    valMap.put(key+"@"+val,res);
                    map.get(val).add(key);
                    valMap.put(val+"@"+key,1/res);
                }

            }
            flag++;
        }
        System.out.println(map);
        System.out.println(valMap);
        return resArrays;
    }
    private double findValue(String key,String value,double res){
        if(map.get(key).contains(value))
            return res*valMap.get(key+"@"+value);


        for(String newkey:map.get(key)){

            if(!isRouter.get(newkey)){
                isRouter.replace(newkey,true);
                double ans = findValue(newkey,value,res*valMap.get(key+"@"+newkey));
                isRouter.put(newkey,false);
                if(ans != -1)
                    return ans;
            }

        }
        return -1;
    }

    public String decodeString(String s) {

        LinkedList<Character> characters = new LinkedList<>();
        LinkedList<String> strings = new LinkedList<>();
        String ans = "";

        for(int i = 0;i<s.length();i++){
            Character character = s.charAt(i);
            if(character=='[') {
                characters.push(character);
                continue;
            }
            if(strings.isEmpty()){
                strings.push(Character.toString(character));
                continue;
            }

            if(character==']'){
                String repeatString = strings.pop();
                Integer repeatNum = Integer.parseInt(strings.pop());
                String tempString = "";
                for(int n = 0;n<repeatNum;n++){
                    tempString = tempString+repeatString;
                }
                if(!strings.isEmpty()){
                    if(isStringToInteger(strings.peek()))
                    {
                        strings.push(tempString);
                    }else {
                        String ConcateString = strings.pop();
                        ConcateString = ConcateString+tempString;
                        strings.push(ConcateString);
                    }
                }else
                    ans = ans+tempString;

                continue;
            }

            if(Character.isDigit(character)){
                String CtoS = character.toString();
                if(s.charAt(i-1)!='['&&isStringToInteger(strings.peek()))
                {
                    String temp = strings.pop();
                    temp = temp+CtoS;
                    strings.push(temp);
                }
                else
                    strings.push(CtoS);
                continue;

            }else {
                String CtoS = character.toString();
                if(!isStringToInteger(strings.peek())){
                    String temp = strings.pop();
                    temp = temp+CtoS;
                    strings.push(temp);
                }
                else
                    strings.push(CtoS);
                continue;

            }
        }
        while (!strings.isEmpty()){
            ans = ans + strings.pop();
        }
        System.out.println(strings);
        System.out.println(characters);
        System.out.println(ans);

        return ans;

    }
    private boolean isStringToInteger(String s){
        try {
            Integer.parseInt(s);
            return true;
        }catch (Exception e)
        {
            return false;
        }

    }

    /**
     * 未完成
     * @param root
     * @param targetSum
     * @return
     */
    public int pathSum(TreeNode root, int targetSum) {
        treeMap = new HashMap<>();
        return 0;
    }
    private int getSumPath(TreeNode root){
        if(root==null)
            return 0;
        int sumRight = getSumPath(root.right)+root.val;
        int sumLeft = getSumPath(root.left)+root.val;

        return sumRight;

    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        if(nums.length<=1)
            return false;
        for(int i = 0;i<nums.length;i++){
            sum = sum+nums[i];
        }
        if(sum%2!=0)
            return false;
        int targetNum = sum/2;
        Arrays.sort(nums);

        return findTargetNum(nums,targetNum);

    }
    private boolean findTargetNum(int[] nums,int targetNum){
        int [][] dp = new int[nums.length][targetNum+1];
        for(int i = 0;i<dp.length;i++)
        {
            if(i==0)
            {
                for(int j = 1;j<dp[0].length;j++)
                {
                    if(j<nums[i])
                        dp[i][j] = 0;
                    else
                        dp[i][j] = nums[i];
                }
                continue;
            }

            for (int j = 1;j<dp[0].length;j++)
            {
                if(j<nums[i])
                {
                    dp[i][j] = dp[i-1][j];
                }
                else
                {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
                }
            }
            if(dp[i][targetNum]==targetNum)
                return true;
        }
        return false;
    }

    public int countSubstrings(String s) {
        if(s.length()==1)
            return 1;
        boolean[][] dp = new boolean[s.length()][s.length()];
        int counter = 0;
        int row = 0;
        int col = 0;
        int colCounter = 0;
        while (true)
        {
            if(col==s.length())
            {
                col = colCounter+1;
                colCounter++;
                if(colCounter==s.length())
                    break;
                row = 0;
            }

            if(col-row<=1){
                if(s.charAt(row)==s.charAt(col))
                {
                    dp[row][col]=true;
                    counter++;
                }
            }else {
                if(s.charAt(row)==s.charAt(col)&&dp[row+1][col-1])
                {
                    dp[row][col] = true;
                    counter++;
                }
            }
            row++;
            col++;

        }
        return counter;

    }

    public boolean searchMatrix(int[][] matrix,int target){
        for(int i = 0;i<matrix.length;i++){
            if(matrix[i][0]==target)
                return true;
            if(matrix[i][0]<target)
            {
                if(binarySearchInMaxtrix(matrix[i],target))
                    return true;
            }
            if(matrix[i][0]>target)
                break;
        }
        return false;
    }
    private boolean binarySearchInMaxtrix(int[] nums,int target){
        int left= 0;
        int right = nums.length-1;

        while (right>left)
        {
            int mid = (right+left)/2;
            if(nums[mid]==target)
                return true;
            if(nums[mid]<target)
            {
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        if(left==right&&nums[right]==target)
            return true;
        return false;
    }

    public int findUnsortedSubarray(int[] nums){
        
        return 0;
    }

    public int maxProfitII(int[] prices){
        if(prices.length==1)
            return 0;
        int maxProfit = 0;
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        System.out.println(dp[0][0]+" "+dp[0][1]);
        for(int i = 1;i<prices.length;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            System.out.println(dp[i][0]+" "+dp[i][1]);
        }

        return dp[prices.length-1][0];
    }

    public int maxProfitIII(int[] prices){
        int maxProfit = 0;
        return maxProfit;
    }

    public void flatten(TreeNode root){
        transTreeToList(root);
    }
    private void transTreeToList(TreeNode root){
        if(root==null)
            return;
        transTreeToList(root.left);
        if(root.left!=null)
        {
            TreeNode tempNode = root.right;
            root.right = root.left;
            TreeNode tempRoot = root;
            while (tempRoot.right!=null)
            {
                tempRoot = tempRoot.right;
            }
            tempRoot.right = tempNode;
            root.left = null;
            transTreeToList(tempNode);
            return;
        }
        transTreeToList(root.right);
        return;
    }

    public List<TreeNode> generateTrees(int n) {
        
        return null;
    }

    /**
     * 错误解法
     * @param n
     * @param primes
     * @return
     */
    public int nthSuperUglyNumberError(int n, int[] primes) {
        if(n==1)
            return 1;
        int[] res = new int[n];
        res[0] = 1;
        Arrays.sort(primes);
        res[1] = primes[0];
        int primesIndex = 1;
        int resIndex = 1;
        for(int i = 2;i<n;i++)
        {
            int valRes = res[1]*res[resIndex];
            if(primesIndex==primes.length)
            {
                permesOutOfIndex(i,resIndex,res);
                break;
            }

            if(valRes<primes[primesIndex])
            {
                res[i] = valRes;
                resIndex++;
            }
            else
            {
                res[i] = primes[primesIndex];
                primesIndex++;
            }

        }
        Main.showArrays(res);
        return res[n-1];
    }
    private void permesOutOfIndex(int index,int resIndex,int[] res){

        for(int i = index;i<res.length;i++){
            res[i] = res[1]*res[resIndex];
            resIndex++;
        }
    }
    public int nthSuperUglyNumberOffical(int n, int[] primes) {
        int[] dp = new int[n + 1];
        int m = primes.length;
        int[] pointers = new int[m];
        int[] nums = new int[m];
        Arrays.fill(nums, 1);
        for (int i = 1; i <= n; i++) {
            int minNum = Arrays.stream(nums).min().getAsInt();
            dp[i] = minNum;
            for (int j = 0; j < m; j++) {
                if (nums[j] == minNum) {
                    pointers[j]++;
                    nums[j] = dp[pointers[j]] * primes[j];
                }
            }
        }
        Main.showArrays(dp);
        return dp[n];
    }

    /**
     * 力中暴力，递归解法，粪作
     * @param n
     * @return
     */
    public int countArrangement(int n){
        boolean[] isChoose = new boolean[n+1];
        int[] counter = new int[1];
        isCountArrangement(n,1,isChoose,counter);
        return counter[0];
    }
    private void isCountArrangement(int n,int index,boolean[] isChoose,int[] counter){
        if(index==n+1){
            counter[0]++;
            return;
        }
        for (int i = 1;i<=n;i++)
        {
            if(!isChoose[i]&&(i%index==0||index%i==0))
            {
                isChoose[i] = true;
                isCountArrangement(n,index+1,isChoose,counter);
                isChoose[i] = false;
            }
        }
        return;
    }
    public int countArrangementOffical(int n){
        int stateNum = 1<<n;
        int [][] dp = new int[n+1][stateNum];
        dp[0][0] = 1;
        for(int i = 1;i<=n;i++)
        {
            for(int state = 0;state<stateNum;state++)
            {
                for(int k = 1;k<=n;k++)
                {
                    if((state>>(k-1)&1)==0)continue;
                    if(k%i!=0&&i%k!=0)continue;
                    dp[i][state]=dp[i-1][state&(~(1<<(k-1)))]+dp[i][state];
                }
            }
        }
        return dp[n][stateNum-1];
    }
    public int counteArrangementSelf(int n){
        int stateNum = 1<<n;
        System.out.println(stateNum);
        int [][] dp = new int[n+1][stateNum];
        dp[0][0] = 1;
        for(int i = 1;i<=n;i++)
        {
            for(int state = 0;state<stateNum;state++)
            {
                for(int k = 1;k<=n;k++)
                {
                    if((1<<(k-1)&state)==1)continue;
                    if(k%i!=0&&i%k!=0)continue;
                    System.out.println(state+1<<(k-1));
                    dp[i][state+(1<<(k-1))] = dp[i-1][state]+dp[i][state+(1<<(k-1))];
                }
            }
        }
        return dp[n][stateNum-1];
    }

    public int numberOfArithmeticSlices(int[] nums){
        if(nums.length<=2)
            return 0;
        int [] dp = new int[nums.length];
        LinkedList<Integer> list = new LinkedList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        dp[0] = nums[1] - nums[0];
        int counter = 1;
        int ans = 0;

        for(int i = 1;i<nums.length;i++)
        {
            dp[i] = nums[i] - nums[i-1];
            if(dp[i]!=dp[i-1])
            {
                Integer integer = map.get(counter);
                if(integer==null)
                {
                    map.put(counter,caculatorNumber(counter));
                }
                ans = ans+map.get(counter);
                counter = 2;
            }else
                counter++;
        }
        if(counter>=3)
        {
            ans = ans+(map.get(counter)==null?caculatorNumber(counter):map.get(counter));
        }
        Main.showArrays(dp);
        System.out.println();

        return ans;
    }
    private int caculatorNumber(int length){
        int sum = 0;
        for(int i = 3;i<=length;i++){
            sum = sum+(length-i+1);
        }
        return sum;
    }
    public int numberOfArithmeticSlicesOffical(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }

        int d = nums[0] - nums[1], t = 0;
        int ans = 0;
        // 因为等差数列的长度至少为 3，所以可以从 i=2 开始枚举
        for (int i = 2; i < n; ++i) {
            if (nums[i - 1] - nums[i] == d) {
                ++t;
            } else {
                d = nums[i - 1] - nums[i];
                t = 0;
            }
            ans += t;
        }
        return ans;
    }

    public int eraseOverlapIntervals(int[][] intervals) {

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0]==0?o1[1] - o2[1]:o1[0] - o2[0];
            }
        });


        return 0;
    }

    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length+1][m + 1][n + 1];
        for(int i = 1;i<=strs.length;i++){
            int [] ZerosOnes = getZerosOnes(strs[i-1]);
            for(int j = 0;j<=m;j++){
                for (int k = 0;k<=n;k++){
                    if(j>=ZerosOnes[0]&&k>=ZerosOnes[1])
                        dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-ZerosOnes[0]][k-ZerosOnes[1]]+1);
                }
            }
        }
        return dp[strs.length][m][n];
    }
    private int[] getZerosOnes(String str){
        int[] res = new int[2];
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)=='0')
                res[0]++;
            else
                res[1]++;
        }
        return res;
    }

    public boolean PredictTheWinner(int[] nums) {

        return total(nums,0,nums.length-1,1)>=0;
    }
    private int total(int[] nums,int start,int end,int turn){
        if(start==end){
            return nums[start]*turn;
        }
        int scoreStart = nums[start]*turn+total(nums,start+1,end,-turn);
        int scoreEnd = nums[end]*turn+total(nums,start,end-1,-turn);
        return Math.max(scoreEnd,scoreStart)*turn;
    }

    public int[][] generateMatrix(int n) {

        int l=0,r = n-1,b = n-1,t = 0;
        int[][] matrix = new int[n][n];
        int num = 1;
        while (num<=n*n){
            for(int i = l;i<=r;i++){
                matrix[t][i] = num++;
            }
            t++;
            for(int i = t;i<=b;i++){
                matrix[i][r] = num++;
            }
            r--;
            for(int i = r;i>=l;i--){
                matrix[b][i] = num++;
            }
            b--;
            for(int i = b;i>=t;i--){
                matrix[i][l] = num++;
            }
            l++;
        }
        return matrix;
    }
    public int[][] generateMatrixMySelf(int n){
        int[][] matrix = new int[n][n];
        int flag = 0;
        int num = 1;
        int x = 0,y = 0;

        while (num<=n*n)
        {
            if(flag>3)
                flag = 0;
            if(flag==0)
            {
//                num++;
                while (y<n&&matrix[x][y]==0)
                {
                    matrix[x][y] = num;
                    num++;
                    y++;
                }
                y--;
                x++;
                flag++;
                continue;
            }
            if(flag==1)
            {
//                num++;
                while (x<n&&matrix[x][y]==0)
                {
                    matrix[x][y] = num;
                    num++;
                    x++;
                }
                flag++;
                x--;
                y--;
                continue;
            }
            if(flag==2)
            {
//                num++;
                while (y>=0&&matrix[x][y]==0)
                {
                    matrix[x][y] = num;
                    num++;
                    y--;
                }
                y++;
                x--;
                flag++;
                continue;
            }
            if(flag==3)
            {
//                num++;
                while (x>=0&&matrix[x][y]==0)
                {
                    matrix[x][y] = num;
                    num++;
                    x--;
                }
                x++;
                y++;
                flag++;
                continue;
            }
        }
        return matrix;
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        int n = matrix.length;
        int m = matrix[0].length;
        int flag = 0;
        int num = 1;
        int x = 0,y = 0;

        while (num<=n*m)
        {
            if(flag>3)
                flag = 0;
            if(flag==0)
            {
                while (y<m&&matrix[x][y]<=100)
                {
                    list.add(matrix[x][y]);
                    matrix[x][y] = 101;
                    num++;
                    y++;
                }
                y--;
                x++;
                flag++;
                continue;
            }
            if(flag==1)
            {
                while (x<n&&matrix[x][y]<=100)
                {
                    list.add(matrix[x][y]);
                    matrix[x][y] = 101;
                    num++;
                    x++;
                }
                flag++;
                x--;
                y--;
                continue;
            }
            if(flag==2)
            {
                while (y>=0&&matrix[x][y]<=100)
                {
                    list.add(matrix[x][y]);
                    matrix[x][y] = 101;
                    num++;
                    y--;
                }
                y++;
                x--;
                flag++;
                continue;
            }
            if(flag==3)
            {
                while (x>=0&&matrix[x][y]<=100)
                {
                    list.add(matrix[x][y]);
                    matrix[x][y] = 101;
                    num++;
                    x--;
                }
                x++;
                y++;
                flag++;
                continue;
            }
        }
        return list;
    }

    public ListNode rotateRight(ListNode head, int k) {
        if(k==0||head==null)
            return head;
        HashMap<Integer, ListNode> listNodeHashMap = new HashMap<>();
        int flag = 0;
        while (head!=null){
            flag++;
            listNodeHashMap.put(flag,head);
            head = head.next;
        }
        return flag>k?rotate(listNodeHashMap,flag,k):rotate(listNodeHashMap,flag,k%flag);
    }
    private ListNode rotate(HashMap<Integer,ListNode> listNodeHashMap,int flag,int k){
        if(k==0)
            return listNodeHashMap.get(1);
        listNodeHashMap.get(flag-k).next=null;
        listNodeHashMap.get(flag).next = listNodeHashMap.get(1);
        return listNodeHashMap.get(flag+1-k);
    }

    public void setZeroes(int[][] matrix){
        HashSet<Integer> xSet = new HashSet<>();
        HashSet<Integer> ySet = new HashSet<>();
        for(int x = 0;x<matrix.length;x++)
        {
            for (int y = 0;y<matrix[0].length;y++)
            {
                if(matrix[x][y]==0)
                {
                    ySet.add(y);
                    xSet.add(x);
                }
            }
        }

        for(int x:xSet){
            for(int y = 0;y<matrix[0].length;y++){
                matrix[x][y]=0;
            }
        }
        for(int y:ySet){
            for(int x = 0;x<matrix.length;x++){
                matrix[x][y]=0;
            }
        }

    }
    public void setZeroesOffical(int[][] matrix){
        int row = matrix.length;
        int col = matrix[0].length;
        boolean row0_flag = false;
        boolean col0_flag = false;
        // 第一行是否有零
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }
        // 第一列是否有零
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }
        // 把第一行第一列作为标志位
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 置0
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (row0_flag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }

    }

    public List<List<Integer>> combine(int n,int k){
        List<List<Integer>> list = new LinkedList<>();
        LinkedList<Integer> subList = new LinkedList<>();
        findList(list,subList,n,k,1);
        return list;
    }
    private void findList(List<List<Integer>> list,LinkedList<Integer> subList,int n,int k,int begin){
        if(subList.size()==k){
            list.add(new LinkedList<>(subList));
            return;
        }
        for(int i=begin;i<=n;i++){
            subList.add(i);
            findList(list,subList,n,k,i+1);
            subList.removeLast();
        }
        return;
    }

    /**
     *粪作
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums){
        int flag = 0;
        int tempNum = 0;
        int counter = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0;i<nums.length;i++){
            if(i==0){
                flag++;
                tempNum = nums[i];
                list.add(nums[i]);
                continue;
            }
            if(nums[i]!=tempNum)
            {
                flag = 1;
                tempNum = nums[i];
                list.add(nums[i]);
            }
            else if(nums[i]==tempNum)
            {
                flag++;
                if(flag==3)
                {
                    nums[i] = 0;
                    flag--;
                    counter++;
                }else
                {
                    tempNum = nums[i];
                    list.add(nums[i]);
                }

            }
        }
        int index = 0;
        for(int i:list){
            nums[index] = i;
            index++;
        }
        return list.size();
    }
    public int removeDuplicatesOffical(int[] nums){
        int n = nums.length;
        if (n <= 2) {
            return n;
        }
        int slow = 2, fast = 2;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
    public int removeDuplicatesSelf(int[] nums){
        if(nums.length<=2)
            return nums.length;
        int slow = 2;
        int fast = 2;
        int counter = 0;
        while (fast<nums.length&&slow<nums.length)
        {
            if(nums[slow-2]==nums[slow])
            {
                while (fast<nums.length&&nums[fast]==nums[slow])
                    fast++;
                if(fast==nums.length&&nums[fast-1]==nums[slow])
                    return slow;
                nums[slow] = nums[fast];
                slow++;
                fast++;
                continue;
            }
            slow++;
        }
        return slow;
    }

    public ListNode deleteDuplicates(ListNode head){
        LinkedList<ListNode> list = new LinkedList<>();
        ListNode tempHead = head;
        while(head!=null)
        {
            if(list.size()==0)
                list.push(head);
            else
            {
                if(head.val!=list.peek().val)
                    list.push(head);
                else
                {
                    while (head!=null&&head.val==list.peek().val)
                        head = head.next;
                    ListNode node = list.pop();
                    if(list.size()!=0)
                    {
                        list.peek().next = head;
                        list.push(head);
                    }
                    else {
                        node.next = null;
                        list.push(head);
                        tempHead = head;
                    }
                }
            }
            if(head!=null)
                head = head.next;
        }
        return tempHead;
    }

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        LinkedList<int[]> list = new LinkedList<>();
        for(int[] nums:intervals)
        {
            if(list.isEmpty())
                list.addLast(nums);
            else
            {
                int[] temp = list.getLast();
                if(nums[0]>temp[1]){
                    list.addLast(nums);
                }else {
                    int right = nums[1]>temp[1]?nums[1]:temp[1];
                    int [] newMerge = new int[]{nums[0],right};
                    list.removeLast();
                    list.addLast(newMerge);
                }
            }
        }

        int [][] res = new int[list.size()][2];
        int index = 0;
        for(int[] nums:list)
        {
            res[index] = nums;
            index++;
        }
        return res;
    }

    public int search(int[] nums, int target) {

        int n = nums.length;
        if(target>nums[n-1]&&target<nums[0])
            return -1;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }

        if(target>=nums[0])
        {
            int left = 0;
            int right = n - 1;
            while (left<=right)
            {
                int mid = (left+right)/2;
                if(nums[mid]>target)
                {

                }
            }
        }
        else
        {

        }
        return 0;
    }

    public boolean searchMatrixNew(int[][] matrix,int target){
        int x = matrix.length;
        int y = matrix[0].length;
        int right = x*y-1;
        int left = 0;
        while (right<=left)
        {
            int fakeMid = (right+left)/2;
            int rowNumber = fakeMid/y;
            int colNumber = fakeMid%x;
            if(matrix[rowNumber][colNumber]==target)
                return true;
            if(matrix[rowNumber][colNumber]>target)
            {
                right = fakeMid-1;
            }
            else
            {
                left = fakeMid+1;
            }
        }
        return false;
    }

    /**
     * 超时
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleave(String s1,String s2,String s3){
        int index1 = 0;
        int index2 = 0;
        int index3 = 0;
        while (index3<s3.length())
        {
            char c1 = index1<s1.length()?s1.charAt(index1):'1';
            char c2 = index2<s2.length()?s2.charAt(index2):'1';
            char c3 = s3.charAt(index3);
            if(c1==c3&&c2!=c3)
            {
                index1++;
                index3++;
            }else if(c2==c3&&c1!=c3)
            {
                index3++;
                index2++;
            }
            else if(c1==c3&&c2==c3)
            {
                index3++;
                index1++;
                boolean MatchIndex1 = isInterleave(s1.substring(index1, s1.length()), s2.substring(index2, s2.length()), s3.substring(index3, s3.length()));
                if(MatchIndex1)
                    return true;
                index1--;
                index2++;
                boolean MatchIndex2 = isInterleave(s1.substring(index1, s1.length()), s2.substring(index2, s2.length()), s3.substring(index3, s3.length()));
                if(MatchIndex2)
                    return true;
                else
                    return false;
            }
            else
                return false;
        }
        return true;
    }
    public boolean isInterleaveOffical(String s1,String s2,String s3){
        int x = s1.length();
        int y = s2.length();
        int m = s3.length();
        boolean[][] dp = new boolean[x+1][y+1];
        dp[0][0] = true;
        for(int i = 0;i<=x;i++)
        {
            for(int j = 0;j<=y;j++)
            {
                int index = i+j-1;
                if(i>0)
                {
                    dp[i][j] = dp[i][j]||(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(index));
                }
                if(j>0)
                {
                    dp[i][j] = dp[i][j]||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(index));
                }
            }
        }
        return dp[x][y];
    }

    public int climbStairs(int n){
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i<=n;i++)
        {
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    public int[][] insert(int[][] intervals,int[] newInterval){

        return null;
    }

    public boolean isSubsequence(String s, String t) {

        int n = s.length();
        int m = t.length();
        if(n>m)
            return false;
        int x = 0;
        int y = 0;
        while (y<m)
        {
            if(x==n)
                return true;
            if(s.charAt(x)==t.charAt(y))
            {
                x++;
                y++;
            }else
                y++;
        }
        return false;
    }

    public int longestOnes(int[] nums, int k){
        int left = 0;
        int right = 0;

        HashMap<Integer, Integer> hashMap = new HashMap<>(1);
        hashMap.put(0,0);

        int maxLen = Integer.MIN_VALUE;

        while (right<nums.length)
        {
            if(nums[right]==1){
                maxLen = Math.max(maxLen,right-left+1);
                right++;
                continue;
            }

            else
            {
                if(hashMap.get(0)<k)
                {
                    hashMap.put(0,hashMap.get(0)+1);
                    maxLen = Math.max(maxLen,right-left+1);
                    right++;
                    continue;
                }
                else
                {
                    while (hashMap.get(0)==k&&right>left)
                    {
                        if(nums[left]==0){
                            break;
                        }
                        left++;
                    }

                    if(right==left){
                        right++;
                        left = right;
                        maxLen = Math.max(maxLen,0);
                        continue;
                    }
                    left++;
                    maxLen = Math.max(maxLen,right-left+1);
                    right++;
                }
            }
        }
        return maxLen;
    }

    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;

        for(int i = 0;i<nums.length;i++)
        {
            sum = sum+nums[i];
            while (sum>=target)
            {
                sum = sum-nums[left];
                res = Math.min(res,i-left+1);
                left++;
            }

        }


        return res==Integer.MAX_VALUE?0:res;

    }

    public int totalFruit(int[] fruits) {
        int res = 0;
        int left = 0;
        HashMap<Integer,Integer> fruitsMap = new HashMap<Integer,Integer>();

        for(int right = 0;right<fruits.length;right++){
            fruitsMap.put(fruits[right],fruitsMap.getOrDefault(fruits[right],0)+1);

            while (fruitsMap.size()>2){
                if(fruitsMap.get(fruits[left])-1==0)
                    fruitsMap.remove(fruits[left]);
                else
                    fruitsMap.put(fruits[left],fruitsMap.get(fruits[left])-1);
                left++;
            }

            if(fruitsMap.size()<=2)
            {
                res = Math.max(res,right-left+1);
            }
        }
        return res;
    }

    public int trap(int[] height) {
        if(height.length<=2)
            return 0;

        LinkedList<Integer> queue = new LinkedList<>();
        int res = 0;
        queue.addLast(0);
        for(int i = 1;i<height.length;i++){
            if(height[i]<height[queue.getFirst()])
                queue.addLast(i);
            else {
                int sum = 0;
                int peekIndex = queue.removeFirst();
                queue.addLast(i);
                while (queue.size()>1){
                    int nextIndex = queue.removeFirst();
                    sum = sum + height[peekIndex] - height[nextIndex];
                }
                res = res+sum;
            }
        }

        if(queue.size()>1){
            int maxIndex = queue.removeFirst();
            queue = new LinkedList<>();
            queue.addLast(height.length-1);
            for(int i = height.length-2;i>=maxIndex;i--){
                if(height[i]<height[queue.getFirst()])
                    queue.addLast(i);
                else {
                    int sum = 0;
                    int peekIndex = queue.removeFirst();
                    queue.addLast(i);
                    while (queue.size()>1){
                        int nextIndex = queue.removeFirst();
                        sum = sum + height[peekIndex] - height[nextIndex];
                    }
                    res = res+sum;
                }
            }
        }
        return res;

    }

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
            String s = String.format("批次:%d  左边:%d  右边:%d  高度:%d  面积:%d",i,left[i],right[i],heights[i],ans);
            System.out.println(s);
        }
        return ans;
    }

    public int minCostClimbingStairs(int[] cost) {
        if(cost.length==2)
            return Math.min(cost[0],cost[1]);
        int[] dp = new int[cost.length+1];

        for(int i = 2;i<=cost.length;i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }

    public int integerBreak(int n) {
        int[] dp = new int[n+1];

        for(int i = 2;i<=n;i++){
            for(int j = 1;j<=i/2;j++){
                int res = Math.max(j,dp[j])*Math.max(i-j,dp[i-j]);
                dp[i] = Math.max(res,dp[i]);
            }
        }

        return dp[n];
    }

    public boolean canPartitionII(int[] nums) {
        if(nums.length<=1)
            return false;
        int sum = 0;
        for(int i = 0;i<nums.length;i++){
            sum = nums[i]+sum;
        }
        if(sum%2!=0)
            return false;

        int[] dp = new int[sum/2+1];

        for(int i = 0;i<nums.length;i++){
            for(int j = dp.length-1;j>=1;j--){

                if(j>=nums[i])
                {
                    dp[j] = Math.max(dp[j-nums[i]]+nums[i],dp[j]);
                }

            }
            if(dp[sum/2] == sum/2)
                return true;
        }
        return false;
    }





















}
